package leetcode_121_140;

public class canCompleteCircuit_134 {
    /**
     * 加油站问题
     * 详见leetcode134
     * @param gas 第 i 个加油站有汽油 gas[i] 升。
     * @param cost 从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升
     * @return 如果可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1
     */
    public int canCompleteCircuit(int[] gas, int[] cost) {
        /**
         * 想法是动态规划
         * 参考了高解思路
         * 3ms
         */
        int dp[] = new int[gas.length]; //第 1 个加油站开到第 i 个加油站时的剩余油量(不算第 i 个加油站的油)
        dp[0] = 0;

        int remain[] = new int[gas.length];  //第 i 个加油站开往第 i+1 个加油站的节余油量
        int mount = 0;
        for (int i = 0; i < gas.length; i++) {
            remain[i] = gas[i] - cost[i];
            mount += remain[i];
        }
        if (mount < 0)
            return -1;

        //只要mount>0,一定存在解，并且是唯一解（题目说明）
        //因此，解就是总油量最低点的下一个点，因为总（gas-cost）是大于等于0的
        // 所以前面损失的gas从最低点下一个点开始都会拿回来
        int minIndex=0;
        for (int i = 1; i < gas.length; i++){
            dp[i] = dp[i - 1] + remain[i - 1];
            if(dp[i]<dp[minIndex])
                minIndex=i;
        }
        return minIndex;
    }

    /**
     * 精简版本
     */
    public int canCompleteCircuit2(int[] gas, int[] cost) {
        int n = gas.length;
        int sum = 0;
        int minSum = Integer.MAX_VALUE, minSumIndex = 0;

        for (int i = 0; i < n; i++){
            sum += gas[i] - cost[i];

            if (sum < minSum){
                minSumIndex = i;
                minSum = sum;
            }
        }
        if (sum < 0) return -1;
        else if (minSum >= 0) return 0;
        else return (minSumIndex + 1) % n;
    }
}
